import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 873. 最长的斐波那契子序列的长度
 * https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/
 */
public class Solutions_873 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};  // output: 5  {1, 2, 3, 5, 8}

//        int[] nums = {1, 3, 7, 11, 12, 14, 18};
        // output: 3  {{1, 11, 12}, {3, 11, 14}, {7, 11, 18}}

//        int[] nums = {2, 4, 7, 8, 9, 10, 14, 15, 18, 23, 32, 50};
        // output: 5  {{4, 14, 18, 32, 50}}

        int result = lenLongestFibSubseq(nums);
        System.out.println(result);
    }

    /**
     * 解法二：动态规划（33ms）
     * 若有 A[l] = 3, A[r] = 5，A[i] = 8（l < r < i）
     * 那么 dp[5][8] = 3，以 5 和 8 结尾的子序列组成的斐波纳契数列长度最短为 3，即 dp[3][5] + 1
     */
    public static int lenLongestFibSubseq(int[] A) {
        int res = 0;
        int len = A.length;
        // dp[2][4] = 4，以 A[2], A[4] 结尾的子序列的最大斐波那契数列长度为 4
        int[][] dp = new int[len][len];
        for (int[] arr : dp) {
            // 默认为 2，即两个元素的长度
            Arrays.fill(arr, 2);
        }
        // 从第 3 个元素开始遍历，每次从 [0, i - 1] 中取 2 个元素，判断是否可以组成斐波纳契数列
        for (int i = 2; i < len; i++) {
            int l = 0, r = i - 1;
            while (l < r) {
                int sum = A[l] + A[r];
                if (sum == A[i]) {
                    // 即 A[l], A[r], A[i] 可以组成一个长度为 3 的斐波纳契数列
                    // 取 dp[l][r] + 1，即 dp[r][i] 的长度，就是在 dp[l][r] 的长度上，再加上 A[i] 所在的 1 个长度
                    dp[r][i] = Math.max(dp[r][i], dp[l][r] + 1);
                    // 记录最大长度
                    res = Math.max(res, dp[r][i]);
                    r --;
                    l ++;
                } else if (sum > A[i]) {
                    // sum 值过大，右指针左移
                    r --;
                } else {
                    // sum 值过小，左指针右移
                    l ++;
                }
            }
        }
        return res;
    }

    /**
     * 解法一：暴力法 + Set 集合（91ms）
     * 解题思路：两层 for 循环，查找第三个数是否在数组中存在，若存在，则迭代继续查找
     */
    public static int lenLongestFibSubseq2(int[] A) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : A) {
            set.add(num);
        }
        int len = A.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                // 两个数，则长度为 2
                int max = 2;
                int a = A[i], b = A[j], next = a + b;
                while (set.contains(next)) {
                    // 迭代查找 next 是否存在
                    a = b;
                    b = next;
                    next = a + b;
                    // 长度加 1
                    max ++;
                }
                // 记录最大长度
                res = Math.max(res, max);
            }
        }
        // 长度小于 3，不是斐波纳契数列
        return res >= 3 ? res : 0;
    }
}
